#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/2/28 4:01 PM
# @Author  : huxiaoman
# @File    : 22_GenerateParentheses.py
# @Package : LeetCode
# @E-mail  : charlotte77_hu@sina.com


class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        def generate(p,left,right):
            if right >= left >=0:
                if not right:
                    yield p
                for q in generate(p+'(' ,left-1,right):yield q
                for q in generate(p+')',left,right -1):yield q
        return list(generate('',n,n))

if __name__ == "__main__":
    s = Solution()
    print s.generateParenthesis(3)